using System;
using System.Collections.Generic;

namespace opt.Analysis.Set
{
	public class BitSet
	{
		private List<Int32> bits;

		public BitSet()
		{
			Clear();
		}

		public BitSet(List<Int32> set)
		{
			if(set == null)
				bits = new List<Int32>();
			else
				bits = new List<Int32>(set);
		}

		public int Count
		{
			get
			{
				return bits.Count * 32;
			}
		}

		public List<Int32> GetSet()
		{
			return new List<Int32>(bits);
		}

		public List<Int32> GetNumberSet()
		{
			List<Int32> ret = new List<Int32>();

			int num = 0;
			int count = bits.Count;
			int i,j;
			int b;
			for(i = 0;i < count;i++)
			{
				b = bits[i];
				if(b != 0)
				{
					for(j = 0;j < 32;j++)
					{
						if(((b>>j)&0x1) == 1)
						{
							ret.Add(num+j);
						}
					}
				}

				num += 32;
			}

			return ret;
		}

		public void Clear()
		{
			bits = new List<Int32>();
		}

		public void Set(int index)
		{
			if(index < 0)
				new ArgumentException("Index cannot be negative.");
			int jump = index/32;
			int offset = index%32;

			if(jump >= bits.Count)
			{
				int new_parts = jump - bits.Count + 1;
				int i;
				for(i = 0;i < new_parts;i++)
					bits.Add(0);
			}
			
			bits[jump] = bits[jump] | (0x1<<offset);
		}

		public void Unset(int index)
		{
			if(index < 0)
				new ArgumentException("Index cannot be negative.");
			int jump = index/32;
			int offset = index%32;

			if(jump < bits.Count)
			{
				bits[jump] = bits[jump] & (~(0x1<<offset));
			}
		}

		public bool IsSet(int index)
		{
			if(index < 0)
				new ArgumentException("Index cannot be negative.");
			int jump = index/32;
			int offset = index%32;

			if(jump < bits.Count)
				return ((bits[jump]>>offset)&0x1) == 0x1;
			return false;
		}

		public BitSet Remove(BitSet input)
		{
			if(input == null)
				new ArgumentException("Input bitset cannot be null.");
			List<Int32> input_set = input.GetSet();
			List<Int32> output_set = new List<Int32>();
		
			int this_count = bits.Count;
			int input_count = input_set.Count;
			if(this_count < input_count)
			{
				while(this_count < input_count)
				{
					bits.Add(0);
					this_count++;
				}
			}
			else if(input_count < this_count)
			{
				while(input_count < this_count)
				{
					input_set.Add(0);
					input_count++;
				}
			}
			int i;
			for(i = 0;i < this_count;i++)
			{
				output_set.Add(bits[i] & (~input_set[i]));
			}

			return new BitSet(output_set);
		}

		public BitSet Intersect(BitSet input)
		{
			if(input == null)
				new ArgumentException("Input bitset cannot be null.");
			List<Int32> input_set = input.GetSet();
			List<Int32> output_set = new List<Int32>();
			
			int this_count = bits.Count;
			int input_count = input_set.Count;
			if(this_count < input_count)
			{
				while(this_count < input_count)
				{
					bits.Add(0);
					this_count++;
				}
			}
			else if(input_count < this_count)
			{
				while(input_count < this_count)
				{
					input_set.Add(0);
					input_count++;
				}
			}
			int i;
			for(i = 0;i < this_count;i++)
			{
				output_set.Add(bits[i] & input_set[i]);
			}

			return new BitSet(output_set);
		}

		public BitSet Union(BitSet input)
		{
			if(input == null)
				new ArgumentException("Input bitset cannot be null.");
			List<Int32> input_set = input.GetSet();
			List<Int32> output_set = new List<Int32>();
			
			int this_count = bits.Count;
			int input_count = input_set.Count;
			if(this_count < input_count)
			{
				while(this_count < input_count)
				{
					bits.Add(0);
					this_count++;
				}
			}
			else if(input_count < this_count)
			{
				while(input_count < this_count)
				{
					input_set.Add(0);
					input_count++;
				}
			}
			int i;
			for(i = 0;i < this_count;i++)
			{
				output_set.Add(bits[i] | input_set[i]);
			}

			return new BitSet(output_set);
		}

		public override bool Equals(Object o)
		{
			if(o is BitSet)
			{
				BitSet temp = (BitSet)o;
				List<Int32> temp_nums = temp.GetNumberSet();
				List<Int32> nums = GetNumberSet();
				if(temp_nums.Count != nums.Count)
					return false;
				int i;
				for(i = 0;i < temp_nums.Count;i++)
					if(!nums.Contains(temp_nums[i]))
						return false;
				/*
				List<Int32> set = temp.GetSet();
				if(set.Count != bits.Count)
					return false;

				int i;
				for(i = 0;i < bits.Count;i++)
					if(bits[i] != set[i])
						return false;
				*/
				return true;
			}
			return false;
		}
		
		public override int GetHashCode()
		{
			return bits.GetHashCode();
		}

		/*
		public void Print()
		{
			Console.WriteLine("Write BitSet Start");
			int i;
			for(i = 0;i < bits.Count;i++)
			{
				Console.WriteLine(bits[i]);
			}
			Console.WriteLine("Write BitSet End");
		}
		*/
	}
}
